#include <bits/stdc++.h>
using namespace std;

/*
2197. 替换数组中的非互质数
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums 。请你对数组执行下述操作：

从 nums 中找出 任意 两个 相邻 的 非互质 数。
如果不存在这样的数，终止 这一过程。
否则，删除这两个数，并 替换 为它们的 最小公倍数（Least Common Multiple，LCM）。
只要还能找出两个相邻的非互质数就继续 重复 这一过程。
返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。

生成的测试用例可以保证最终数组中的值 小于或者等于 108 。

两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的 最大公约数 。

 

示例 1 ：

输入：nums = [6,4,3,2,7,6,2]
输出：[12,7,6]
解释：
- (6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。
- (12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。
- (12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。
- (6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。
现在，nums 中不存在相邻的非互质数。
因此，修改后得到的最终数组是 [12,7,6] 。
注意，存在其他方法可以获得相同的最终数组。
示例 2 ：

输入：nums = [2,2,1,1,3,3,3]
输出：[2,1,1,3]
解释：
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。
- (2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。
现在，nums 中不存在相邻的非互质数。 
因此，修改后得到的最终数组是 [2,1,1,3] 。 
注意，存在其他方法可以获得相同的最终数组。
 

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 105
生成的测试用例可以保证最终数组中的值 小于或者等于 108 。
*/

// 法一
class Solution {
public:
    using ll = long long;
    // helper 辗转相除
    int gcd(int a, int b) {
        while (b != 0) {
            int tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    vector<int> replaceNonCoprimes(vector<int>& nums) {
        // stack?
        vector<int> stack; 
        for (int num : nums) {
            int cur = num;  // 合并后的LCM or org的item
            // 迭代检查 当前元素与栈顶元素是否非互质
            while (!stack.empty()) {
                int top = stack.back();
                int com = gcd(top, cur);

                // 非互质的情况 合并
                if (com > 1) {
                    stack.pop_back();
                    // 最小公倍数的LCM  注意溢出问题
                    ll lcm = (ll)top / com * cur;
                    cur = (int)lcm;
                } else  break;
            }
            stack.push_back(cur);
        }
        return stack;
    }
};

// 法二
class Solution {
public:
    using ll = long long;
    // helper 辗转相除 helper递归更爽
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    vector<int> replaceNonCoprimes(vector<int>& nums) {
        // stack?
        vector<int> stack; 
        for (int num : nums) {
            int cur = num;  // 合并后的LCM or org的item
            // 迭代检查 当前元素与栈顶元素是否非互质
            while (!stack.empty()) {
                int top = stack.back();
                int com = gcd(top, cur);

                // 非互质的情况 合并
                if (com > 1) {
                    stack.pop_back();
                    // 最小公倍数的LCM  注意溢出问题
                    ll lcm = (ll)top / com * cur;
                    cur = (int)lcm;
                } else  break;
            }
            stack.push_back(cur);
        }
        return stack;
    }
};

// 尝试主函数不使用stack 也递归试试
// 不行 只能优化
// 法三
class Solution {
public:
    using ll = long long;
    // helper 辗转相除 迭代效率大于递归
    int gcd(int a, int b) {
        while (b) {
            a %= b;
            swap(a, b);
        }
        return a;
    }

    vector<int> replaceNonCoprimes(vector<int>& nums) {
        // stack √  这里使用双栈优化
        vector<int> stack; 
        int top = 0; // 双指针：top指向当前有效元素的末尾（模拟栈顶）
        for (int i = 1; i < nums.size(); ++i) {
            int current = nums[i]; // 当前待处理元素
            
            // 与前面的有效元素（模拟栈）反复合并
            while (top >= 0) {
                int prev = nums[top]; // 前一个有效元素（栈顶）
                int common = gcd(prev, current);
                if (common > 1) { // 非互质，合并
                    // 计算LCM，先除后乘避免溢出
                    long long lcm = (long long)prev / common * current;
                    current = (int)lcm;
                    top--; // 弹出栈顶（合并后原栈顶失效）
                } else      break; // 互质，停止合并
            }
            // 将合并后的元素放入有效区域（栈顶+1）
            nums[++top] = current;
        }
        
        // 截取有效区域作为结果
        return vector<int>(nums.begin(), nums.begin() + top + 1);
    }
};